//题目:
// 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
// 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
// 问总共有多少条不同的路径？
#include<iostream>
#include<vector>
#include<map>

using namespace std;
//代码:
class Solution 
{
    int ret=0;
    int m,n;
    int dx[2]={1,0},dy[2]={0,1};
    map<pair<int,int>,int> mp;//备忘录
public:
    //暴力搜索（超时）
    // void dfs(int row,int col)
    // {
    //     if(row==m-1 && col==n-1){
    //         ret++;
    //         return;
    //     }
    //     for(int i=0;i<2;i++)
    //     {
    //         int x=row+dx[i],y=col+dy[i];
    //         if(x>=0 && x<m && y>=0 && y<n)
    //             dfs(x,y);
    //     }
    // }
    // int uniquePaths(int _m, int _n) 
    // {
    //     m=_m,n=_n;
    //     dfs(0,0);
    //     return ret;
    // }

    //记忆化搜索
    int dfs(int row,int col)
    {
        if(row==m-1 && col==n-1){
            return 1;
        }
        if(mp.count({row,col}))return mp[{row,col}];

        int count=0;
        for(int i=0;i<2;i++)
        {
            int x=row+dx[i],y=col+dy[i];
            if(x>=0 && x<m && y>=0 && y<n)
                count+=dfs(x,y);
        }
        mp[{row,col}]=count;//记录(row,col)这个位置走向finish有多少种走法
        return count;
    }
    int uniquePaths(int _m, int _n) 
    {
        m=_m,n=_n;
        return dfs(0,0);
    }
};